package com.topvision.myviewtest.algorithm.sort;


/**
 * @FileName : MergeSort.java
 * @Author : Zero_Tzz
 * @E-mail : 497847377@qq.com
 * @Data : 2018-07-03 23:28
 * @Describe : 归并排序 O（n*logn）
 */
public class MergeSort extends BaseSort {

    /**
     * 递归使用归并排序，对arr[l..r]的范围进行排序(均为闭区间)
     */
    public static Integer[] sort() {
        Integer[] arr = generateRandomArray();
        mergeSort(arr, 0, arr.length - 1);
        return arr;
    }


    private static void mergeSort(Integer[] arr, int l, int r) {

        if (l >= r) return;

        // 取中间值
        int mid = (l + r) / 2;

        // 递归 - 依次排序左边
        mergeSort(arr, l, mid);
        // 递归 - 依次排序右边
        mergeSort(arr, mid + 1, r);
        // 递归- 依次归并数组
        merge(arr, l, mid, r);
    }

/** 图示理解法2333:
 2,4,6,1
 |   |
 2,4 6,1
 | | | |
 2 4 6 1 // 直到单个元素 对应 if (l >= r) return; 此时二分递归停止 开始执行 merge(arr, l, mid, r);
 |   |
 2,4 1,6 // 递归倒序执行 - 先执行最低层（深度）排序，依次往上执行，直到归并完成
 |
 1,2,4,6
 */

    /**
     * 细分数组之后，开始归并排序 （将arr[l..mid]和arr[mid+1..r]两部分进行归并）
     */
    private static void merge(Integer[] arr, int l, int mid, int r) {
        // 注意：此方法中的l 为偏移量 即需要排序的起始位置，通常为0
        // 定义临时数组(长度跟arr一样 r-l+1)
        Integer[] aux = new Integer[r - l + 1];

        // 复制数据到该数组
        for (int i = l; i <= r; i++) {
            // 临时变量起始位置为0，所以需要减去偏移量
            aux[i - l] = arr[i];
        }

        // 定义三个指针
        int i = l; // 左边起始位置
        int j = mid + 1; // 右边起始位置
        int k = l; // 临时数组起始位置
        for (; k <= r; k++) {
            // 需要判断越界情况
            if (i > mid) {
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i - l];
                i++;
            }
            // 判断临时数组（需要减去偏移量）左边第一个元素和右边第一个元素的大小，更小的元素赋值给原数组的第k的索引,被赋值的临时数组位置需要自增一次
            else if (aux[i - l] > aux[j - l]) {
                arr[k] = aux[j - l];
                j++;
            } else {
                arr[k] = aux[i - l];
                i++;
            }
        }
    }
}
